//剑指 Offer 40. 最小的k个数
/**
 * 1.直接排序
 * 2.使用快排的变形
 * 3.使用小顶堆
 */

void quick_sort(int arr[], int l, int r, int k) 
{
	int tmp, i = l, j = r;
	if (i < j) {
		tmp = arr[i];	//取arr[i]，i位置空
		while (i != j) {
			while (i < j && arr[j] >= tmp) j--;	//向左靠
			arr[i] = arr[j];	//取arr[j]填arr[i]，j位置空
			while (i < j && arr[i] < tmp ) i++;
			arr[j] = arr[i]; 	//取arr[i]填arr[j]，i位置空	
		}
		arr[i] = tmp; 
        if (k == i) return ;
		else if (i > k) //继续去左边切分
		    quick_sort(arr, l, i-1, k);
        else 
		    quick_sort(arr, i+1, r, k);
	}
}

int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){
    int i = 0, *num = malloc(sizeof(int)*k);
    quick_sort(arr, 0, arrSize-1, k-1); //要找的数为下标k-1
    memcpy(num, arr, sizeof(int)*k);
    *returnSize = k;
    return num;
}